package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 不同路径
        Solution solution1 = new Solution();
        System.out.println("不同路径:");
        System.out.println("m=3, n=7: " + solution1.uniquePaths(3, 7)); // 28
        System.out.println("m=3, n=2: " + solution1.uniquePaths(3, 2)); // 3

        // 测试用例 - 不同路径II
        Solution2 solution2 = new Solution2();
        System.out.println("\n不同路径II:");
        int[][] obstacleGrid1 = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        System.out.println("示例1: " + solution2.uniquePathsWithObstacles(obstacleGrid1)); // 2
        int[][] obstacleGrid2 = {{0, 1}, {0, 0}};
        System.out.println("示例2: " + solution2.uniquePathsWithObstacles(obstacleGrid2)); // 1
    }

    // 不同路径
    static class Solution {
        int[][] dp;

        public int uniquePaths(int m, int n) {
            dp = new int[m + 1][n + 1];
            dp[1][1] = 1;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (j == 1 && i == 1) {
                        dp[i][j] = 1;
                        continue;
                    }
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }

            return dp[m][n];
        }
    }

    // 不同路径II
    static class Solution2 {
        int[][] dp;
        int m, n;

        public int uniquePathsWithObstacles(int[][] num) {
            m = num.length;
            n = num[0].length;
            dp = new int[m + 1][n + 1];
            if (num[0][0] == 1) return 0;
            dp[1][1] = 1;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (j == 1 && i == 1) {
                        continue;
                    }

                    if (num[i - 1][j - 1] == 1) {  // 当前格子是障碍
                        dp[i][j] = 0;        // 到不了，路径数是0
                    } else {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  // 直接加
                    }
                }
            }

            return dp[m][n];
        }
    }
}